%%%-------------------------------------------------------------------
%%% File    : p16.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% 2^(15) = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
%%% What is the sum of the digits of the number 2^(1000)?
%%%
%%% Created :  5 Dec 2008 by  <>
%%%-------------------------------------------------------------------
-module(p16).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: solution(Power) -> int
%% Description: Returns the sum of the digits of 2**Power
%%--------------------------------------------------------------------
solution(Power) ->
    pow2sum(Power, [1]).

%%====================================================================
%% Internal functions
%%====================================================================
%% If we have a list of the digits of a number, multiplication by 2
%% is equal to doubling the digits in the list and handling the cary 
%% over. So 2**Power is equal to starting with [1] and doubling
%% it Power times
pow2sum(0, Acc)->
    lists:sum(Acc);
pow2sum(N, Acc)->
    pow2sum(N-1, digits_double(Acc)).

%%Returns the digits resulting of the multiplication by 2
digits_double(Digits) ->
    digits_double(lists:reverse(Digits), 0, []).
digits_double([], 0, Acc) -> Acc;
digits_double([], 1, Acc) -> [1|Acc];
digits_double([H|T], Rem, Acc) ->
    Double = 2*H + Rem,
    digits_double(T, Double div 10, [Double rem 10|Acc]).
